import java.util.*;

public class PrefixSum {

    public static void main(String[] args) {
        System.out.println((-51 % 5 + 5)%5);
        System.out.println((51 % 5 + 5) % 5);
        System.out.println();
        String s = "aa";
        System.out.println((int)(Math.log(32)/Math.log(2)));
//        for(char i: s.toCharArray()){
//
//        }
    }

    /**
     * 消失的两个数字
     * 只出现一次的数字和只出现一次的数字III的结合
     * 把1-n的数字和给的数字加载一起 那么就获得了一个数组，这个数组是只有俩个数字只出现了一次 而其他数字出现了俩次
     * 这样使用只出现一次的数字III的解法来机行
     */
    public int[] missingTwo(int[] nums) {
        int n = nums.length;int v1 = 0;
        for(int i = 1 ;i <= n; i++){
            v1 ^= nums[i-1];
            v1 ^= i;
        }
        v1 ^= n+1;v1 ^= n+2;
        int lowBit = v1 & -v1;
        //在给全部异或在一起
        int a = 0; int b = 0;
        for(int i : nums){
            if((i & lowBit)!=0){
                a ^= i;
            }else{
                b ^= i;
            }
        }
        for(int i = 1; i <= n+2; i++){
            if((i & lowBit)!=0){
                a ^= i;
            }else{
                b ^= i;
            }
        }
        return new int[]{a,b};
    }

    /**
     * 只出现一次的数字 II
     */

    public int singleNumberBe(int[] nums) {
        int ret = 0;
        for(int i = 0; i < 32;i++){
            int sum = 0;
            for(int x : nums)
                if(((x>>i)&1)==1)
                    sum++;
            if(sum %3==1)
                ret|=(1<<i);
        }
        return ret;
    }

    public int singleNumber(int[] nums) {
        int[] count = new int[32];
        for(int i : nums){
            while(i!=0){
                int lowBit = i&-i;
                if(lowBit<0){
                    count[31]++;
                    break;
                }
                int index = (int)(Math.log(lowBit)/Math.log(2));
                count[index]++;
                i &= i-1;
            }
        }
        int ret = 0;
        for(int i = 0; i < 32; i++){
            if(count[i] % 3 == 1){
                ret |= (1<<i);
            }
        }
        return ret;
    }
    /**
     * 两整数之和
     * 位运算加法
     */
    public int getSum(int a, int b) {
        int n1 = a ^ b;
        int n2 = (a & b) << 1;
        while(n2 != 0){
            a = n1; b = n2;
            n1 = a ^ b;
            n2 = (a & b) << 1;
        }
        return n1;
    }
    /**
     * 丢失的数字
     */
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for(int i = 0; i < n; i++){
            sum^=i;
            sum^=nums[i];
        }
        sum ^= n;
        return sum;
    }

    /**
     * 判定字符是否唯一
     * 位图 鸽巢原理
     */
    public boolean isUnique(String astr) {
        int n = astr.length();
        //鸽巢原理
        if(n > 26) return false;
        int hash = 0;

//      位图
        for(char i : astr.toCharArray()){
            if(is1(hash,i-'a')) return false;
            hash = to1(hash,i-'a');
            // System.out.println("hash = "+hash+" i-'a' = "+ (i-'a'));
        }
        return true;
    }

    // 00110
// 00010
// 00010 != 0
    boolean is1(int hash, int index){
        // System.out.println("is1 hash = "+hash+" index= "+ index);
        return (hash & (1<<index)) != 0;
    }

    // 00110
// 00001
    int to1(int hash, int index){
        // System.out.println("to1 hash = "+hash+" index= "+ index);
        return (hash | (1 << index));
    }
    /**
     * 矩阵区域和
     */
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int n = mat[0].length;
        int m = mat.length;
        int[][] dp = new int[m + 1][n + 1];

        for (int y = 1; y < m + 1; y++) {
            for (int x = 1; x < n + 1; x++) {
                dp[y][x] = dp[y - 1][x] + dp[y][x - 1] - dp[y - 1][x - 1] + mat[y - 1][x - 1];
            }
        }

        for (int y = 0; y < n + 1; y++) {
            System.out.println(Arrays.toString(dp[y]));
        }

        // System.out.println();

        int[][] ret = new int[m][n];
        for (int y = 0; y < m; y++) {
            for (int x = 0; x < n; x++) {
                int x1 = Math.max(x - k, 0);
                int y1 = Math.max(y - k, 0);
                int x2 = Math.min(x + k + 1, n);
                int y2 = Math.min(y + k + 1, m);
                // System.out.println("x1 = " + x1 + " y1 = " + y1 + " x2 = " + x2 + " y2 = " + y2);
                ret[y][x] = dp[y2][x2] - dp[y1][x2] - dp[y2][x1] + dp[y1][x1];
                // System.out.println("ret = " + Arrays.toString(ret[y]));
                // System.out.println();
            }
        }

        // System.out.println("ret");
        // for (int y = 0; y < n; y++) {
        //     System.out.println(Arrays.toString(ret[y]));
        // }

        return ret;
    }

    /**
     * 连续数组
     */
    public int findMaxLength(int[] nums) {
        int ret = 0, pre = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0,0);
        for (int i = 1; i <= nums.length; i++) {
            pre += nums[i - 1] == 0 ? -1 : 1;
            int f = map.getOrDefault(pre, i);
            if(f != i){
                ret = Math.max(i - f, ret);
            }else{
                map.put(pre, i);
            }
        }
        return ret;
    }

    /**
     *  和可被 K 整除的子数组
     *  同于定理  (a-b)/k=p....0 ==> a%p=b%p 同余定理
     *  复负去%的结果修正 (cur%k+k)%k
     */

    public int subArraysDivByK(int[] nums, int k) {
        int pre = 0, ret = 0;
        // Map<Integer,Integer> map = new HashMap<>();
        int[] map = new int[k];
        map[0] = 1;
        // map.put(0,1);
        for(int i : nums){
            int cur = pre + i;
            int v = (cur%k+k)%k;
            //(a-b)/k=p....0 ==> a%p=b%p 同余定理
            // ret += map.getOrDefault(v,0);
            ret += map[v];
            map[v]++;
            // map.put(v,map.getOrDefault(v,0)+1);
            pre = cur;
        }
        return ret;
    }
    /**
     * 除自身以外数组的乘积
     */
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] pre = new int[n+1];
        int[] aft = new int[n+1];
        pre[0] = 1; aft[n] = 1;
        for(int i = 1; i < n+1; i++){
            pre[i] = pre[i-1] * nums[i-1];
        }

        for(int i = n-1; i >= 0; i--){
            aft[i] = aft[i+1] * nums[i];
        }

        // System.out.println("pre = "+  Arrays.toString(pre)+ " aft = "+ Arrays.toString(aft));

        int[] ret = new int[n];
        for(int i = 1; i < n + 1; i++){
            ret[i-1] = pre[i-1] * aft[i];
        }
        return ret;
    }

    /**
     * 和为 K 的子数组
     */
    public int subarraySum(int[] nums, int k) {
        int pre = 0, ret = 0;
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        for(int i : nums){
            int cur = pre + i;
            ret += map.getOrDefault(cur-k,0);
            map.put(cur,map.getOrDefault(cur,0)+1);
            pre = cur;
        }
        Set<Integer> set = map.keySet();
        return ret;
    }
    /**
     * 寻找数组的中心下标
     */
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n+1];
        int sum = 0;
        for(int i = 0; i < n;i++){
            sum += nums[i];
            dp[i+1] = nums[i] + dp[i];
        }
        // System.out.println(Arrays.toString(dp));
//        Arrays.toString()
        for(int i = 1; i <= n; i++){
            // System.out.println("i = "+i);
            if(dp[i-1]==dp[n]-dp[i]) return i-1;
        }
        return -1;
    }
    /**
     * 二维前缀和
     */
    public static void TwoMain(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int m = in.nextInt();
            long t = in.nextLong();
            long[][] dp = new long[n+1][m+1];
            for(int y = 1;y <= n; y++){
                for(int x = 1; x <= m; x++){
                    long v = in.nextLong();
                    dp[y][x] = dp[y-1][x]+dp[y][x-1]+v-dp[y-1][x-1];
                }
            }
            for(long i = 0; i < t; i++){
                int y1 = in.nextInt();
                int x1 = in.nextInt();
                int y2 = in.nextInt();
                int x2 = in.nextInt();
                System.out.println(dp[y2][x2]-dp[y1-1][x2]-dp[y2][x1-1]+dp[y1-1][x1-1]);
            }
        }
    }
    /**
     * 一维前缀和
     */

    public int[] runningSum(int[] nums) {
        int n = nums.length;
        int[] ret = new int[n];
        ret[0] = nums[0];
        for(int i = 1;i<n;i++){
            ret[i]=ret[i-1]+nums[i];
        }
        return ret;
    }
}
